package priorityqueue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;



 class Student implements Comparable<Student>{//不实现Comparator接口，加第1个不报错，第2个开始报错
    public int age;

     public Student(int age) {
         this.age = age;
     }

     @Override
     public int compareTo(Student o) {
         return o.age-this.age;
     }

     @Override
     public String toString() {
         return "Student{" +
                 "age=" + age +
                 '}';
     }
 }
 class IntCmp implements Comparator<Integer>{

     @Override
     public int compare(Integer o1,Integer o2) {
         return o2-o1;
     }
 }
public class Test {
    public static void main(String[] args) {
        int[] array={27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap=new TestHeap();
        testHeap.createHeap(array);//时间复杂度:O(n)
        testHeap.heapSort();
        System.out.println("调试用");
    }
    /**
     * top-k问题，解决思路
     * 1.对整个数组进行排序，然后取前十个元素
     * 2.借助堆来进行操作
     * 2.1先将整体元素，建成最大堆
     * 2.2出队3次，这3个就是最大的
     * 3.利用快排的划分过程
     */
    /**
     * 时间复杂度：O(n*logn)
     * @param array
     * @param k
     * @return
     */
     public static int[] topk1(int[] array,int k){
         IntCmp intCmp = new IntCmp();
         PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(intCmp);//存Integer且大根堆
         //n*logn
         for (int i = 0; i <array.length ; i++) {
             priorityQueue.offer(array[i]);//插入堆中
         }
         //大堆创建完毕 n*logn
         int[] ret = new int[k];
         for (int i = 0; i < k; i++) {
             int val = priorityQueue.poll();
             ret[i]=val;
         }
         return ret;
     }

    /**
     * 前k个最大的元素思路
     * 1.先将数组前k个元素建成小根堆
     * 2.从数组的第K+1个元素开始和堆顶进行比较。如果这个元素比堆顶元素小，则弹出堆顶元素，然后将当前数组的元素放入堆中
     * 3.如果当前i下标的元素，大于当前堆顶的值，那么堆顶元素出队，然后将i下标的值入堆
     * 4.直到遍历完整个数组，结束了
     * 同理下面是求最小的K个数的代码
     * 时间复杂度：O(n*logk)
     * @param array
     * @param k
     * @return
     */
    public static int[] topk(int[] array,int k){
        int[] ret = new int[k];
        if(k==0){
            return ret;
        }
        IntCmp intCmp = new IntCmp();
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k,intCmp);//存Integer且大根堆
        for (int i = 0; i < array.length; i++) {
            if(maxHeap.size()<k){
                maxHeap.offer(array[i]);

            }else {
                int top = maxHeap.peek();
                if(array[i]<top){
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }

            }
        }

        for (int i = 0; i < k; i++) {
            int val=maxHeap.poll();
            ret[i]=val;
        }
        return ret;
    }
    public static void main5(String[] args) {
         int[] array={10,4,20,19,45,20};
        int[] ret= topk(array,3);
        System.out.println(Arrays.toString(ret));


    }

    
    public static void main4(String[] args) {
        PriorityQueue<Student> priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(new Student(12));
        priorityQueue.offer(new Student(1));
        System.out.println(priorityQueue);



    }
    public static void main3(String[] args) {
        //变大根堆
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1 ;
            }
        });


    }
    public static void main2(String[] args) {
        //默认是小根堆
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        priorityQueue.offer(12);
        priorityQueue.offer(3);
        priorityQueue.offer(78);
        int tmp = priorityQueue.peek();
        System.out.println(tmp);
        System.out.println(priorityQueue.poll());//3
        System.out.println(priorityQueue.poll());//12


    }

    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        testHeap.createHeap(array);
       // testHeap.push(50);
        testHeap.pollHeap();
        System.out.println("7");

    }
}
